/*
 * @Author: szx
 * @Date: 2022-03-25 14:12:14
 * @LastEditTime: 2022-03-25 14:15:20
 * @Description:
 * @FilePath: \leetcode\400-499\494\494_2.js
 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var findTargetSumWays = function (nums, target) {
    const sum = nums.reduce((p, c) => p + c, 0);
    if ((sum + target) % 2 == 1) return 0;
    if (Math.abs(target) > sum) return 0; // 此时没有方案

    const tar = Math.floor((sum + target) / 2);
    // dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
    const dp = new Array(tar + 1).fill(0);
    dp[0] = 1;
    for (let i = 0; i < nums.length; i++) {
        for (let j = tar; j >= nums[i]; j--) {
            // 不放就是上一个的dp[j]种方法数，放就是上一个dp[j-nums[i]]方法数，两者相加。
            dp[j] += dp[j - nums[i]];
        }
    }
    return dp[tar];
};
